// https://leetcode.cn/problems/Jf1JuT/

// 算法思路总结：
// 1. 外星文字典拓扑排序构建字符顺序
// 2. 通过相邻单词比较建立字符间依赖关系
// 3. 构建有向图并计算每个字符的入度
// 4. 使用队列进行拓扑排序得到合法字符序列
// 5. 时间复杂度：O(C)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <cstring>

class Solution 
{
public:
    unordered_map<char, unordered_set<char>> edges;
    unordered_map<char, int> in;

    string alienOrder(vector<string>& words) 
    {
        edges.clear();
        in.clear();

        for (const string& str : words)
        {
            for (const char& ch : str)
            {
                in[ch] = 0;
            }
        }

        for (int i = 0 ; i < words.size() - 1 ; i++)
        {
            if (compare(words[i], words[i + 1]) == false)
            {
                return "";
            }
        }

        string res;
        queue<char> q;
        for (const auto& [ch, num] : in)
        {
            if (num == 0)
            {
                q.push(ch);
            }
        }

        while (!q.empty())
        {
            char ch = q.front();
            q.pop();
            
            res += ch;

            for (const char& dst : edges[ch])
            {
                if (--in[dst] == 0)
                {
                    q.push(dst);
                }
            }
        }

        if (res.size() == in.size())
        {
            return res;
        }
        return "";
    }

    bool compare(string& s1, string& s2)
    {
        int minLen = min(s1.size(), s2.size());
        bool found = false;

        for (int i = 0 ; i < minLen ; i++)
        {
            if (s1[i] != s2[i])
            {
                if (edges[s1[i]].count(s2[i]) == 0)
                {
                    edges[s1[i]].insert(s2[i]);
                    in[s2[i]]++; 
                }
                return true;
            }
        }

        return s1.size() <= s2.size();
    }
};

int main()
{
    vector<string> words1 = {"wrt","wrf","er","ett","rftt"};
    vector<string> words2 = {"z","x"};

    Solution sol;

    cout << sol.alienOrder(words1) << endl;
    cout << sol.alienOrder(words2) << endl;

    return 0;
}